The present invention relates to a system and method for route calculation for use with a navigation system and used with a map database with data attributes.
Computer-based navigation systems are able to provide end users, such as vehicle drivers and other travelers, with various navigating functions and features. For example, some navigation systems are able to determine an optimum route to travel by roads between locations in a geographic region. Using input from the end user, and optionally from equipment that can determine the end user""s physical location (such as a global positioning system), a navigation 15 system can identify and examine various routes between two locations in the geographic region to determine an optimum route between the locations.
The navigation system may then provide the end user with information about the optimum route in the form of instructions that identify the maneuvers required to be taken by the end user to travel from the starting location to the destination location. The navigation system may be located in an automobile and the instructions may take the form of audio instructions that are provided as the end user is driving the route. Some navigation systems are capable of providing detailed moving map displays outlining the route between locations, the types of maneuvers to be taken along the route, locations of certain types of features or points of interest, and so on.
To provide these and other navigating functions, present navigation systems include navigation application software programs and use one or more detailed databases that include data which represent physical geographic navigable features. The detailed database(s) include data representing the road networks in a geographic region, including the roads and intersections in the region and information about the particular roads and intersections, such as one-way streets, turn restrictions at intersections, speed limits along the roads, street names of the various roads, address ranges along the various roads and so on. Further, the data may include information about points-of-interest such as restaurants, hotels, and so on. Presently, the collection of such geographic data and the provision of such data in a computer-usable database format are provided by Navigation Technologies of Chicago, Ill.
Performance can be an important factor that affects the usefulness of some of the features provided by a navigation system. For example, if a navigation system is used by a driver in a moving vehicle to obtain a route to a destination, guidance for following the route is needed relatively quickly, i.e., within several seconds or less, in order to instruct the driver about required maneuvers at upcoming intersections.
Although performance can be an important factor for navigation systems, there are several considerations that can make performance difficult to achieve. One consideration is that some navigation systems, in particular systems installed in vehicles or handheld devices, may have limited resources, such as relatively slow processors, limited memory, etc. Another consideration is that the geographic databases used by navigation systems are relatively large in order to include the types and detail of information needed to provide the features desired by end users. The relatively large sizes of geographic databases used by navigation systems can be difficult to handle, thereby affecting performance.
Techniques have been devised or implemented to improve navigation system performance by organizing, structuring, or arranging the geographic database or the data in the database in particular ways. Because a navigation system uses geographic data in certain known and expected ways to perform known functions, the geographic data can be organized, structured, or arranged in a manner that facilitates their use in these known ways by the navigation system.
Navigation application programs may also run on computer platforms that have relatively more memory resources and faster I/O, such as personal computers or networks. Although these platforms may have more and faster resources, the considerations related to the efficient use of geographic data still apply, but on a different scale. With these types of platforms, even greater functionality can be provided if the geographic database can be formed and used efficiently.
Accordingly, it is an objective to provide improvements in the storage and/or use of geographic data, and/or the programming that uses the geographic data.
To facilitate processing of the geographic data, the exemplary embodiments provide an efficient way for reducing the data necessary for consideration in route calculation. The geographic data in a map database represents navigable features such as roadways and intersections. The navigable features include one or more segments (e.g., to represent roadways), which are connected by nodes (e.g., to represent intersections). The present embodiments provide a concise way to use directionally identified and attributed no-outlet and circular segments in route calculations to facilitate the processing of the geographic data, which can provide quicker computation and results.
In an exemplary embodiment, a route calculation program adapted to find at least one solution route, between a first location and a second location on a road network, identifies a segment with a first node and a second node in the road network. From an attribute stored in the map database, the program determines whether the first node is connected to the road network and the second node is connected to an isolated portion of the road network. Using the attribute, the route calculation program determines whether to explore the isolated portion of the road network.
According to another exemplary embodiment, a method for a route calculation search includes retrieving a data structure in a map database that represents a successor segment with a first node and a second node. The method further includes identifying an attribute in the data structure that identifies the successor segment as a segment that connects a road network at the first node with an isolated portion of the road network at the second node. The route calculation search refrains from exploring the isolated portion of the road network if the search retrieved the successor segment at the first node. Alternatively, the route calculation suppresses a search from exploring segments inside the isolated portion of the road network, and explores the segment and its successor segments if a search identified the segment as a no-outlet segment at the second node.
According to another exemplary embodiment, geographic data are transmitted to an end user""s computing platform and used by the end user""s platform to provide navigation related features to an end user. The method includes transmitting data structures to the end user""s computing platform. Each data structure includes fields with data that represent a segment of a road in a road network, and a data attribute in one of the fields that identifies the segment that connects the road network with an isolated portion of the road network. The end user""s computing platform uses the attribute to determine whether to explore the isolated portions of the road network.
According to another exemplary embodiment, a navigation system includes a map database for storing attributes that identify the segments of roads that connect a road network with an isolated portion of the road network. The navigation system further includes a navigation program for calculating a route between a first location on the road network represented by the map database and a second location on the road network represented by the map database. The navigation program uses the attributes to determine whether to explore the isolated portions of the road network.
Based on the identification as a no-outlet or circular segment, a route calculation program may determine whether to consider the segment and its successor segments, if any. This can provide for an efficient utilization of computer resources in a navigation system application. Moreover, a faster response and shorter wait times in navigation systems may be achieved. Systems with faster response times may also process and/or provide navigation information more quickly.